package 蓝桥杯算法;

import java.util.Arrays;
import java.util.Map;

public class day28 {
    public static void main(String[] args) {
        day28 a=new day28();
       /* int[] arr={1,2,3,0,2};
        System.out.println(a.maxprice(arr));
        int[] price={1, 3, 2, 8, 4, 9};
        System.out.println(a.maxprice2(price,2));
        int[] num={10,9,2,5,3,7,101,18};
        System.out.println(a.lulie(num));*/
        int[] arr2={1,3,5,4,7};
        System.out.println(a.xulie(arr2));
        int[] arr3={1,2,3,2,1};
        int[] arr4={3,2,1,4,7};
        System.out.println(a.maxcover(arr3,arr4));
        String s1="abcde";
        String s2="ace";
        System.out.println(a.findmax(s1,s2));
        int[] arr={1,4,2};
        int[] arr5={1,2,4};
        System.out.println(a.maxnums(arr,arr5));
        int[] arr6={-2,1,-3,4,-1,2,1,-5,4};
        System.out.println(a.maxresult(arr6));
        String s5="abc";
        String s6="ahbgdc";
        String s7="axc";
        String s8="ahbgdc";
        System.out.println(a.ischildren(s5,s6));
        System.out.println(a.ischildren(s7,s8));




    }
    public int maxprice(int[] price){
        if(price.length==0||price==null){
            return 0;
        }
        int[][]dp=new int[price.length][2];
        //卖出
       dp[0][0]=0;
       //买入
       dp[0][1]=-price[0];
       //上一轮的卖出 这一轮的买入和卖出
       dp[1][0]=Math.max(dp[0][0],dp[0][1]+price[1]);
       dp[1][1]=Math.max(dp[0][0]-price[1],dp[0][1]);
        for(int i=2;i<price.length;i++){
            //卖出
            //上一轮的卖出和上一轮的买入和卖出
           dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+price[i]);
           //买入
            //上一轮的买入，上上一轮的卖出和买入
            dp[i][1]=Math.max(dp[i-1][1],dp[i-2][0]-price[i]);
        }
        return dp[price.length-1][0];
    }
    public int maxprice2(int[] price,int fee){
        if(price.length==0||price==null){
            return 0;
        }
        int[][]dp=new int[price.length][2];
        //卖出
        dp[0][0]=0;
        //买入
        dp[0][1]=-price[0];
        for(int i=1;i<price.length;i++){
            //卖出
            dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+price[i]-fee);
            //买入
            dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-price[i]);
        }
        return dp[price.length-1][0];
    }
public int lulie(int[] num){
        if(num.length==0||num==null){
            return 0;
        }
        int[]dp=new int[num.length];
        Arrays.fill(dp,1);
        for(int i=1;i<num.length;i++){
            for(int j=0;j<i;j++){
                if(num[i]>num[j]){
                    dp[i]=Math.max(dp[i],dp[j]+1);
                    //不断选择值最大的序列
                    //不断更新
                }
            }
        }
        return dp[num.length-1];
}
public int xulie(int[] num){
    if(num.length==0||num==null){
        return 0;
    }
    int[]dp=new int[num.length];
    Arrays.fill(dp,1);
    for(int i=0;i<num.length-1;i++){
        if(num[i+1]>num[i]){
            dp[i+1]=dp[i]+1;
        }
    }
    int max=0;
   for(int i=0;i<num.length;i++){
       max= Math.max(max,dp[i]);
   }
return max;
    }
    public int maxcover(int[] num1,int[] num2){
        int[][]dp=new int[num1.length+1][num2.length+1];
        dp[0][0]=0;
        int result=0;
        for(int i=1;i<num1.length+1;i++){
            for(int j=1;j<num2.length+1;j++){
                if(num1[i-1]==num2[j-1]){
                    dp[i][j]=dp[i-1][j-1]+1;
                    //相同则继续相加，不同则重新开始
                    result=Math.max(result,dp[i][j]);
                }
            }
        }
        return result;
       }
    public int findmax(String s1,String s2){
        int[][]dp=new int[s1.length()+1][s2.length()+1];
        char[] c1= s1.toCharArray();
        char[] c2=s2.toCharArray();
        dp[0][0]=0;
        int result=0;
        for(int i=1;i<=c1.length;i++){
            for(int j=1;j<=c2.length;j++){
                //和遍历背包有点相似
                if(c1[i-1]==c2[j-1]){
                   dp[i][j]=dp[i-1][j-1]+1;
                }
                else{//选取值最大的
                    dp[i][j]=Math.max(dp[i][j-1],dp[i-1][j]);
                }
                result=Math.max(result,dp[i][j]);
            }
        }
        return result;
    }
    public int maxnums(int[] nums1,int[] nums2){
      int[][]dp=new int[nums1.length+1][nums2.length+1];
      for(int i=1;i<=nums1.length;i++){
          for(int j=1;j<=nums2.length;j++){
              if(nums1[i-1]==nums2[j-1]){
                  dp[i][j]=dp[i-1][j-1]+1;
              }
              else{
                  dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
              }
          }
      }
      return dp[nums1.length][nums2.length];
    }
    public int maxresult(int[] nums){
        if(nums.length==0||nums==null){
            return 0;
        }
        int res=0;
        int[] dp=new int[nums.length];
        dp[0]=nums[0];
        for(int i=1;i<nums.length;i++){
            dp[i]=Math.max(dp[i-1]+nums[i],nums[i]);
            //每个位置对应了相关的值，选取其中最大的那个
            res=Math.max(res,dp[i]);
        }
        return res;
    }
    public boolean ischildren(String s1,String s2){
        char[] c1=s1.toCharArray();
        char[] c2=s2.toCharArray();
        int[][] dp=new int[c1.length+1][c2.length+1];
        for(int i=1;i<=c1.length;i++){
            for(int j=1;j<=c2.length;j++){
                if(c1[i-1]==c2[j-1]){
                    dp[i][j]=dp[i-1][j-1]+1;
                }
                else{
                    dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
       return dp[c1.length][c2.length]==c1.length;
    }
}




